70.爬楼梯

题目

70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

动态规划求解

1. 确定 dp[] 及下标含义: dp[i]表示第i阶有几种爬楼梯的方法
2. 确定递推公式: dp[i]=dp[i-1]+dp[i-2]
3. 确定 dp[] 如何初始化: dp[1]=1、dp[2]=2
4. 确定遍历顺序: 已知 dp[1]、dp[2] 求 dp[i]，故为顺序遍历
5. 举例推导 db[]: 当 i=5 时，dp[] 为 1、2、3、5、8、13

func climbStairs(n int) int {
	if n < 3 {
		return n
	}

	dp := make([]int, n+1)
	dp[1], dp[2] = 1, 2
	for i := 3; i < n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}

	return dp[n]
}